package org.czl.leetcode4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class l3419 {
    public static void main(String[] args) {
        //[[1,0,1],[2,0,2],[3,0,1],[4,3,1],[2,1,1]]
        System.out.println(minMaxWeight(5, new int[][]{{1, 0, 1}, {2, 0, 2}, {3, 0, 1}, {4, 3, 1}, {2, 1, 1}}, 2));
    }
    public static int minMaxWeight(int n, int[][] edges, int threshold) {
        ArrayList[] path = new ArrayList[n];
        for(int i = 0; i < n; i++){
            path[i] = new ArrayList<>();
        }
        for(int[] arr : edges){
            int y = arr[0];
            int x = arr[1];
            int w = arr[2];
            path[x].add(new int[]{y, w});
        }
        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[0] = 0;
        boolean[] set = new boolean[n];
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        queue.add(new int[]{0 ,0});
        while(!queue.isEmpty()){
            int[] ret = queue.poll();
            int x = ret[0];
            int w = ret[1];
            if(set[x])continue;
            set[x] = true;
            for(Object t : path[x]){
                int[] to = (int[]) t;
                int newD = Math.max(to[1], w);
                if(newD < dis[to[0]]){
                    dis[to[0]] = newD;
                    queue.add(new int[]{to[0], newD});
                }
            }
        }
        int ans = Integer.MIN_VALUE;
        for(int i : dis){
            if(i == Integer.MAX_VALUE)return -1;
            ans = Math.max(i, ans);
        }
        return ans;
    }
}
